from functools import cache


class Solution:

    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:

        mod = 1000000007

        def f(num_str: str) -> int:

            num = [int(c) for c in num_str]

            @cache
            def g(index, isceil, tot):
                if index == len(num):
                    return min_sum <= tot <= max_sum
                if tot > max_sum:
                    return 0
                ceil = num[index] if isceil else 9
                ans = 0
                for i in range(ceil + 1):
                    ans += g(index + 1, isceil and i == ceil, tot + i)
                return ans % mod

            return g(0, True, 0)

        return (f(num2) + mod - f(num1) +
                (min_sum <= sum(map(int, num1)) <= max_sum)) % mod


so = Solution()
print(so.count(num1="1", num2="12", min_sum=1, max_sum=8) == 11)
print(so.count(num1="1", num2="5", min_sum=1, max_sum=5) == 5)
print(so.count("1000000007", "2000000014", 1, 400) == 1)

from typing import *


class Solution:

    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        mod = 1000000007
        n = len(num2)

        def num_array(num: str, n: int) -> List[int]:
            array = [0] * n
            i = n - 1
            for c in num[::-1]:
                array[i] = int(c)
                i -= 1
            return array

        floor = num_array(num1, n)
        ceil = num_array(num2, n)

        @cache
        def f(index: int, bound: int, tot: int) -> int:
            if index == n:
                return min_sum <= tot <= max_sum
            if tot > max_sum:
                return 0

            L = floor[index] if bound & 1 == 1 else 0
            R = ceil[index] if bound & 2 == 2 else 9
            ans = 0
            for i in range(L, R + 1):
                next_bound = (1 if i == L and bound & 1 == 1 else
                              0) | (2 if i == R and bound & 2 == 2 else 0)
                ans += f(index + 1, next_bound, tot + i)
            return ans % mod

        return f(0, 3, 0) % mod


so = Solution()
print(so.count(num1="1", num2="12", min_sum=1, max_sum=8) == 11)
print(so.count(num1="1", num2="5", min_sum=1, max_sum=5) == 5)
print(so.count("1000000007", "2000000014", 1, 400) == 1)


def DigitalDP(self, num1: str, num2: str) -> int:
    from functools import cache
    # [num1,num2]之间数字数量
    mod = 1000000007
    n = len(num2)

    def num_array(num: str, n: int) -> List[int]:
        # 转数组，下界前缀补0
        array = [0] * n
        i = n - 1
        for c in num[::-1]:
            array[i] = int(c)
            i -= 1
        return array

    floor = num_array(num1, n)
    ceil = num_array(num2, n)

    @cache
    def f(index: int, bound: int) -> int:
        if index == n:
            return 1  # 没有业务限制的情况下
        L = floor[index] if bound & 1 == 1 else 0
        R = ceil[index] if bound & 2 == 2 else 9
        ans = 0
        for i in range(L, R + 1):
            next_bound = (1 if i == L and bound & 1 == 1 else
                          0) | (2 if i == R and bound & 2 == 2 else 0)
            ans += f(index + 1, next_bound)
        return ans % mod

    return f(0, 3) % mod  # 0开始，上下界
